/*************************************************************************
	> File Name: 1.red_black_insert.cpp
	> Author: 
	> Mail: 
	> Created Time: 二  4/27 21:40:58 2021
 ************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct Node {
    int key;
    int color; // 0:read,1:black;2:double black
    struct Node *lchild, *rchild;
} Node;

Node __NIL;
#define NIL (&__NIL)

__attribute__((constructor))
void init_NIL() {
    NIL->key = -1;
    NIL->color = 1;
    NIL->lchild = NIL->rchild = NIL;
    return ;
}

Node *getNewNode(int key) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->key = key;
    p->color = 0;
    p->lchild = p->rchild = NIL;
    return p;
}

void clear(Node *root) {
    if (root == NIL) return ;
    clear(root->lchild);
    clear(root->rchild);
    free(root);
    return ;
}

int has_red_child(Node *root) {
    return (root->lchild->color == 0 || root->rchild->color == 0);
}

Node *left_rotate(Node *root) {
    printf("left rotate: %d\n", root->key);
    Node *tmp = root->rchild;
    root->rchild = tmp->lchild;
    tmp->lchild = root;
    return tmp;
}

Node *right_rotate(Node *root) {
    printf("right rotate: %d\n", root->key);
    Node *tmp = root->lchild;
    root->lchild = tmp->rchild;
    tmp->rchild = root;
    return tmp;
}

const char *maintain_str[] = {"", "LL", "LR", "RL", "RR"};
Node *insert_maintain(Node *root) {
    if (!has_red_child(root)) return root;
    if (root->lchild->color == 0 && root->rchild->color == 0) {
        if (!has_red_child(root->lchild) && !has_red_child(root->rchild)) return root;
        printf("Situation 1 : change color \n");
        root->color = 0;
        root->lchild->color = root->rchild->color = 1;
        return root;
    }
    if (root->lchild->color == 0 && !has_red_child(root->lchild)) return root;
    if (root->rchild->color == 0 && !has_red_child(root->rchild)) return root;
    int maintain_type = 0;
    if (root->lchild->color == 0) {
        if (root->lchild->rchild->color == 0) {
            root->lchild = left_rotate(root->lchild);
            maintain_type = 2;
        } else {
            maintain_type = 1;
        }
        root = right_rotate(root);
    } else {
        if (root->rchild->lchild->color == 0) {
            root->rchild = right_rotate(root->rchild);
            maintain_type = 3;
        } else {
            maintain_type = 4;
        }
        root = left_rotate(root);
    }
    printf("Maintain Type : %s\n", maintain_str[maintain_type]);
    root->color = 0;
    root->lchild->color = root->rchild->color = 1;
    return root;
}

Node *__insert(Node *root, int key) {
    if (root == NIL) return getNewNode(key);
    if (key == root->key) return root;
    if (key < root->key) root->lchild = __insert(root->lchild, key);
    else root->rchild = __insert(root->rchild, key);
    return insert_maintain(root);
}

Node *insert(Node *root, int key) {
    root = __insert(root, key);
    root->color = 1;
    return root;
}

void print(Node *root) {
    printf("(%d | %d, %d, %d)\n",
          root->color, root->key,
          root->lchild->key, root->rchild->key);
    return ;
}

void output(Node *root) {
    if (root == NIL) return ;
    print(root);
    output(root->lchild);
    output(root->rchild);
    return ;
}

Node *rand_insert(Node *root) {
    int val = rand() % 100;
    printf("\ninsert %d to red black tree: \n", val);
    root = insert(root, val);
    output(root);
    return root;
}


int main() {
    int n;
    srand(time(0));
    scanf("%d", &n);
    Node *root = NIL;
    for (int i = 0; i < n; i++) {
        root = rand_insert(root);
    }

    return 0;
}
